import java.util.Arrays;

public class Maxheap {
    public static void main(String[] args) {

        int[] array = {2, 3, 1, 7, 6, 4, 5};
        MaxHeap1 heap = new MaxHeap1(array);
        System.out.println(Arrays.toString(heap.array));

        while (heap.size > 1) {
            heap.swap(0, heap.size - 1);
            heap.size--;
            heap.down(0);
        }

        System.out.println(Arrays.toString(heap.array));
    }
}

class MaxHeap1{
    int[] array;
    int size;


    public MaxHeap1(int capacity){
        this.array = new int[capacity];
    }


    /**
     * 获取堆顶元素
     *
     * @return 堆顶元素
     */
    public int peek(){
        return array[0];
    }

    /**
     * 删除堆顶元素
     *
     * @return 堆顶元素
     */
    public int poll(){
        int top = array[0];
        swap(0,size-1);
        size--;
        down(0);
        return top;
    }

    /**
     * 删除指定索引处元素
     *
     * @param index 索引
     * @return 被删除元素
     */
    public int poll(int index){
        int remove = array[index];
        swap(remove,size-1);
        size--;
        down(index);
        return remove;
    }

    /**
     * 替换堆顶元素
     *
     * @param replaced 新元素
     */
    public void replace(int replaced){
        array[0] = replaced;
        down(0);
    }

    /**
     * 堆的尾部添加元素
     *
     * @param offered 新元素
     * @return 是否添加成功
     */
    public boolean offer(int offered){
        if (size==array.length){
            return false;
        }
        up(offered,size);
        size++;
        return true;
    }

    public MaxHeap1(int[] array){
        this.array = array;
        this.size = array.length;
        heapify();
    }


    // 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
    public void up(int offered,int index){
        int child = index;
        while (child>0){
            int parent =  (child-1)/2;
            if (offered > array[parent]){
                array[child] = array[parent];
            }else {
                break;
            }
            child = parent;
        }
        array[child] = offered;
    }

    // 建堆
    public void heapify(){
        // 如何找到最后这个非叶子节点  size / 2 - 1
        for (int i = size/2-1;i>=0;i--){
            down(i);
        }
    }

    //下潜
    public void down(int parent){
        int left = 2 * parent + 1;
        int right = left +1 ;
        int max = parent;
        if (left<size && array[left] > array[max]){
            max = left;
        }
        if (right<size && array[right] > array[max]){
            max = right;
        }
        if (max != parent){
            swap(max,parent);
            down(max);
        }
    }

    public void swap(int i,int j){
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }


}
